Actually you should check the 26 cubes immediately surrounding the cube in
question as well, otherwise particles at the very edge of one cube wouldn't
be influenced by particles at the very edge of the next cube

-tgq


"Chris Jeppesen" <chr### [at] digiquillcom> wrote in message
news:3bcdc15c$1@news.povray.org...
> Well, the basic alogrithm is to find the closest neighboring particle, and
> if it is within a certain distance, generate a force towards this nearest
> neighbor. The slow O(N^2) part is finding the nearest particle.
>
> What if you chopped up the space into cubes, and only looked for a nearest
> neighbor in the same cube? I assume that somewhere deep down in your
> simulation is a 1-dimensional array representing the particles.
>
> Suppose you divided the space into 10x10x10 cubes, and had a 4-dimensional
> array Neighbors[10][10][10][N_PARTICLES]. When the physics loop starts,
the
> array is cleared. When each particle position is updated, calculate which
> cube it belongs in, say <4,5,6> and write that into Neighbors[4][5][6].
Now
> when it comes time to calculate, for each particle only check for its
> nearest neighbor in the same neighbor cube. This could reduce time to
> O(1000*(N/1000)^2).
>

Post a reply to this message